package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;

public class ImplementStrstr {

    /**
     * KMP 算法
     * 比如：
     *  haystack = abababcde，i = 0,
     *  needle   = ababc, j = 0
     *  移动后        ababc
     * 当haystack第一次匹配失败后，i = 4, j = 4
     * 得到next数组为 [0, 0, 1, 1, 2]
     * 所以这次匹配失败后，i = 4, j = 2;
     */
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0){
            return 0;
        }
        int[] next = getNext(needle);
        for (int i = 0, j = 0; i < n; i++) {
            // 匹配不成功 j = next(j - 1)
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            // 整一段匹配成功，直接返回下标
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    /**
     * 获得KMP算法的next数组，
     * next数组代表了当haystack字符串和needle匹配失败后最少移动位数
     * KMP通过编译needle得到最少移动位数，移动位数= 已匹配值 - 最大公共元素长度
     * 满足 s[0: next[j - 1] - 1] = s[i - next[j - 1] - 1 : i - 1]
     */
    private int[] getNext(String needle){
        int m = needle.length();
        int[] next = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }
        return next;
    }

    public static void main(String[] args) {
        String haystack = "a";
        String needle = "a";
        int i = new ImplementStrstr().strStr(haystack, needle);
        System.out.println(i);
        Assert.isTrue(i == 0);
    }
}
